package arithmetic_40;

public class Solution_1 {

	/**
	 * 思路1：可以直接使用236的代码
	 */

	/**
	 * 思路2：借助二叉搜索树的特性，更加简单的写法
	 */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

		// 如果p、q都小于root，那说明p、q的最近公共祖先肯定在左子树里面，继续遍历左子树
		if (p.val < root.val && q.val < root.val) {
			return lowestCommonAncestor(root.left, p, q);
		}
		// 如果p、q都大于root，那说明p、q的最近公共祖先肯定在右子树里面，继续遍历右子树
		if (p.val > root.val && q.val > root.val) {
			return lowestCommonAncestor(root.right, p, q);
		}

		// 只有当p、q分叉（一个在root的左子树里，一个在root的右子树里），那说明当前root就是他们的最近公共祖先
		return root;

	}

	/**
	 * 思路3：思路2的非递归写法
	 */
	public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		while (root != null) {
			if (p.val < root.val && q.val < root.val) {
				// 如果p、q都小于root，那说明p、q的最近公共祖先肯定在左子树里面，继续遍历左子树
				root = root.left;
			} else if (p.val > root.val && q.val > root.val) {
				// 如果p、q都大于root，那说明p、q的最近公共祖先肯定在右子树里面，继续遍历右子树
				root = root.right;
			} else {
				// 只有当p、q分叉（一个在root的左子树里，一个在root的右子树里），那说明当前root就是他们的最近公共祖先
				return root;
			}
		}
		return root;
	}
	
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

}